package org.cabbage.lintcode;

import java.util.Stack;

public class TreeSerialize {

    static String s = null;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node3.left = node4;
        node3.right = node5;
        node5.right = node6;
        String ser = serialize(root);
        System.out.println(ser);
        TreeNode fan = deserialize(ser);
        String ser2 = serialize(fan);
        System.out.println(ser2);
    }

    public static String serialize(TreeNode root) {
        s = "";
        serializeNode(root);
        return s;
    }

    public static void serializeNode(TreeNode node) {
        //int val=node.val;
        s = s + node.val + ";";
        if (node.left != null) {
            s = s + "\\l";
            serializeNode(node.left);
        }
        if (node.right != null) {
            s = s + "\\r";
            serializeNode(node.right);
        }
        s = s + "\\e";
    }

    public static TreeNode deserialize(String data) {
        if (data.equals("")) return null;
        TreeNode root = new TreeNode(0);

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        String[] ss = data.split(";");
        for (String s : ss) {
            boolean isEnd = false;
            while (!isEnd) {
                if (s.startsWith("\\l")) {
                    TreeNode node = new TreeNode(0);
                    stack.peek().left = node;
                    stack.push(node);
                    s = s.substring(2);
                } else if (s.startsWith("\\r")) {
                    TreeNode node = new TreeNode(0);
                    stack.peek().right = node;
                    stack.push(node);
                    s = s.substring(2);
                } else if (s.startsWith("\\e")) {
                    stack.pop();
                    s = s.substring(2);
                } else {
                    if (s != null && !s.equals("")) {
                        stack.peek().val = Integer.parseInt(s);
                    }
                    isEnd = true;
                }
            }

        }
        return root;
    }
}
